package everydayone.subarraysDivByK;

import java.util.HashMap;

/**
 * @Date 2020/05/27
 * @author 王光浩
 * @Thinking 使用前缀和解决。
 * 		需要了解的知识点：同余定理（x-y）Mod z == 0 => x Mod z == y Mod z
 * 		使用方法：
 * 			（1）创建一个 HashMap 对象，key 为 前缀和%K，value 为key 出现的次数
 * 			（2）遍历数组，同时统计前缀和，计算 前缀和%mod 的值，在 HashMap 对象中判断是否存在对应的 key，如果存在则
 * 				 取出对应的 value，将 ret += value；然后 进行put 操作。
 * 		注意事项：在 java 中由于 负数 Mod 正数 为 负数，所以我们需要将这个 Mod出来的负数转化为对应的正数。
 */
public class MyMethodTwo {
	public int subarraysDivByK(int[] A, int K) {
		if (A == null)
			throw new RuntimeException("A数组不能为 null");
		int ret = 0;
		int sum = 0;
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, 1);
		for (int tem : A) {
			sum += tem;
			int val = (sum % K + K) % K;
			ret += map.getOrDefault(val, 0);
			map.put(val, map.getOrDefault(val, 0));
		}
		return ret;
	}
}
